{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Median of a Row Wise Sorted Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: matrixMedian"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #行排序矩阵的中位数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含&nbsp;<strong>奇数&nbsp;</strong>个整数的&nbsp;<code>m x n</code> 矩阵&nbsp;<code>grid</code>，其中每一行按 <strong>非递减 </strong>的顺序排序，返回矩阵的&nbsp;<strong>中位数</strong>。</p>\n",
    "\n",
    "<p>你必须以 <code>O(m * log(n))</code> 的时间复杂度来解决这个问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,2],[2,3,3],[1,3,4]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 矩阵的元素按顺序排列为 1,1,1,2,<u>2</u>,3,3,3,4。中位数是 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,3,3,4]]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 矩阵的元素按顺序排列为 1,1,<u>3</u>,3,4。中位数是 3。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 500</code></li>\n",
    "\t<li><code>m</code> 和&nbsp;<code>n</code>&nbsp;都是奇数。</li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>grid[i]</code> 按非递减顺序排序</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [median-of-a-row-wise-sorted-matrix](https://leetcode.cn/problems/median-of-a-row-wise-sorted-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [median-of-a-row-wise-sorted-matrix](https://leetcode.cn/problems/median-of-a-row-wise-sorted-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,2],[2,3,3],[1,3,4]]', '[[1,1,3,3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # % 二分答案\n",
    "    # O(mlognlogk)\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            cnt = 0\n",
    "            for row in grid:\n",
    "                cnt += bisect_left(row, x)\n",
    "\n",
    "            return cnt <= m * n // 2\n",
    "        \n",
    "        left = min(row[0] for row in grid)\n",
    "        right = max(row[-1] for row in grid)\n",
    "        ans = left\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_ = 0\n",
    "        min_ = 10 ** 6\n",
    "        for i in range(m):\n",
    "            min_ = min(min_, grid[i][0])\n",
    "            max_ = max(max_, grid[i][n - 1])\n",
    "\n",
    "        def count(v):\n",
    "            ret = 0\n",
    "            for i in range(m):\n",
    "                ret += bisect.bisect_left(grid[i], v)\n",
    "            return ret\n",
    "\n",
    "        l = min_\n",
    "        r = max_\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if count(mid) <= m * n // 2:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 二分答案\n",
    "    # O(mlognlogC) C为数字的范围\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            cnt = 0\n",
    "            for row in grid:\n",
    "                cnt += bisect_left(row, x)\n",
    "\n",
    "            return cnt <= m * n // 2\n",
    "\n",
    "        \n",
    "        left = min(row[0] for row in grid)\n",
    "        right = max(row[-1] for row in grid)\n",
    "        ans = left\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def check(x: int) -> bool:\n",
    "            cnt = 0\n",
    "            for row in grid:\n",
    "                cnt += bisect_left(row, x)\n",
    "            return cnt <= m * n // 2\n",
    "        left = min(row[0] for row in grid)\n",
    "        right = max(row[-1] for row in grid)\n",
    "        ans = left\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def valid(self, grid, num, total):\n",
    "        # count how many numbers are strictly\n",
    "        # smaller than num and strictly greater than n\n",
    "        n_smaller = 0\n",
    "        for row in grid:\n",
    "            small_idx = bisect.bisect_left(row, num)\n",
    "            n_smaller += small_idx\n",
    "\n",
    "        return n_smaller <= total // 2\n",
    "\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        # binary search the median\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        k = (n * m) // 2\n",
    "        start = min([row[0] for row in grid])\n",
    "        end = max([row[-1] for row in grid])\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end) // 2\n",
    "            if self.valid(grid, mid, n * m):\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "        if self.valid(grid, start, n * m):\n",
    "            return start\n",
    "        else:\n",
    "            return end\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        minn = min(row[0] for row in grid) \n",
    "        maxn = max(row[-1] for row in grid)\n",
    "\n",
    "        def check(x):\n",
    "\n",
    "            cnt = 0\n",
    "            for row in grid:\n",
    "                cnt += bisect.bisect_left(row,x) \n",
    "            if cnt <= m*n//2:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        left = minn\n",
    "        right = maxn+1\n",
    "        while left<right:\n",
    "            mid = left +(right-left)//2\n",
    "            if check(mid):\n",
    "                left =mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        tmp_list = [item for sub_list in grid for item in sub_list]\n",
    "        tmp_list.sort()\n",
    "\n",
    "        length = len(tmp_list)\n",
    "        if length % 2 == 0:\n",
    "            return (tmp_list[length // 2] + tmp_list[length // 2 - 1]) / 2.0\n",
    "        else:\n",
    "            return tmp_list[length // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_ = 0\n",
    "        min_ = 10 ** 6\n",
    "        for i in range(m):\n",
    "            min_ = min(min_, grid[i][0])\n",
    "            max_ = max(max_, grid[i][n - 1])\n",
    "\n",
    "        def count(v):\n",
    "            ret = 0\n",
    "            for i in range(m):\n",
    "                ret += bisect.bisect_left(grid[i], v)\n",
    "            return ret\n",
    "\n",
    "        l = min_\n",
    "        r = max_\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if count(mid) <= m * n // 2:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                arr.append(grid[i][j])\n",
    "        arr.sort()\n",
    "        return arr[len(arr) // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        a = []\n",
    "        for x in grid:\n",
    "            a += x\n",
    "        n = len(a)\n",
    "        a.sort()\n",
    "        return a[n//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "\r\n",
    "        def check(x: int) -> bool:\r\n",
    "            cnt = 0\r\n",
    "            for row in grid:\r\n",
    "                cnt += bisect_left(row, x)\r\n",
    "            return cnt <= m * n // 2\r\n",
    "        \r\n",
    "        left = min(row[0] for row in grid)\r\n",
    "        right = max(row[-1] for row in grid)\r\n",
    "        ans = left\r\n",
    "        while left <= right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "            if check(mid):\r\n",
    "                left = mid + 1\r\n",
    "                ans = mid\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixMedian(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = min(row[0] for row in grid)\n",
    "        right = max(row[-1] for row in grid)\n",
    "        ans = -1\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for row in grid:\n",
    "                cnt += bisect_left(row, x)\n",
    "            return cnt <= m * n // 2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
